/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int getHeight(struct TreeNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    else
    {
        int left = getHeight(root->left);
        int right = getHeight(root->right);
        int big = left > right ? left : right;
        return big + 1;
    }
}

bool isBalanced(struct TreeNode* root)
{
    if (root == NULL)
    {
        return true;
    }
    int left = getHeight(root->left);
    int right = getHeight(root->right);
    if (left - 1 == right || left + 1 == right || left == right)
    {
        return isBalanced(root->left) && isBalanced(root->right);
    }
    else
    {
        return false;
    }
}